#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    struct DicTree {
        DicTree()
        {
            letter = vector<DicTree*>(26, nullptr);
            is_end = false;
        }
        vector<DicTree*> letter;
        bool is_end;
    };
    DicTree* dic = new DicTree();
    string findRoot(const string& str)
    {
        string res;
        DicTree* node = dic;
        for (auto& c : str)
        {
            if (node->is_end == true)
                return res;
            else if (node->letter[c - 'a'] != nullptr)
            {
                node = node->letter[c - 'a'];
                res += c;
            }
            else
                return str;
        }
        return res;
    }

    void dicInsert(const string& str)
    {
        DicTree* cur = dic;
        for (auto& c : str)
        {
            if (!cur->letter[c - 'a'])
            {
                DicTree* node = new DicTree();
                cur->letter[c - 'a'] = node;
            }
            cur = cur->letter[c - 'a'];
        }
        cur->is_end = true;
    }

    string replaceWords(vector<string>& dictionary, string sentence) {
        for (const auto& str : dictionary)
        {
            dicInsert(str);
        }
        int left = 0;
        string res;
        while (left < sentence.size())
        {
            int right = sentence.find(' ', left);
            if (right != -1)
            {
                res += findRoot(sentence.substr(left, right - left));
                left = right + 1;
            }
            else
            {
                res += findRoot(sentence.substr(left, right - left));
                break;
            }
            res += ' ';
        }
        return res;
    }
};